Masala #1146

Shahar to’g’ri chiziqdan iborat, va bu shaharda mahalliy aholini yangiliklardan xabardor qilish uchun $N$ ta Radio o’rnatilgan. Har bir radioning ovoz balandligi $K$ ga teng. Radioda yangilik eshittirilganda $A$- koordinatada bo’lgan uyga $B$-koordinatada joylashtirilgan radioning ovozi $max(K-|A-B|, 0)$ balandlikda eshitiladi. Sizga $M$ ta uyning koordinatasi beriladi, har bir uy uchun ungacha yetib kelatidan eng baland radio ovozining balandligini aniqlang.

Kirish oqimining dastlabki satrida uchta butun son, $N(1 \le N \le 250000)$, $M(1 \le M \le 250000)$ va $K(1 \le K \le 10^9)$ sonlari kiritiladi. Ikkinchi satrda $N$ ta butun son, $B_i(1 \le i \le N, 0 \le B_i \le 10^9)$ Radiolarning joylashgan koordinatalari kamaymaslik tartibida kiritiladi. Uchinchi satrda M ta butun son, $A_i(1 \le i \le M, 0 \le A_i \le 10^9)$ uylarning joylashgan koordinatalari kiritiladi.

Chiqish oqimida har bir uy uchun alohida qatorda bittadan butun son, berilgan uyga radioning ovozi qanday balandlikda eshitilishini chop eting.